/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/concatenated-string-with-uncommon-characters-of-two-strings
   @Language: C++
   @Datetime: 19-04-25 13:46
   */

// Method 1, union find, Time 625ms
class ConnectingGraph3 {
	vector<int> edges;
	int node;
	int find(int x){
		for(int fx=edges[x]; fx; fx=edges[x=fx]);
		return x;
	}
public:
	ConnectingGraph3(int n){
		edges=vector<int>(n+1,0);
		node=n;
	}
	/**
	 * @param a: An integer
	 * @param b: An integer
	 * @return: nothing
	 */
	void connect(int a, int b) {
		// write your code here
		a=find(a);
		b=find(b);
		if(a==b) continue;
		edges[a]=b;
		--node;
	}

	/**
	 * @return: An integer
	 */
	int query() {
		// write your code here
		return node;
	}
};

// Method 2, weighted union find, Time 490ms
class ConnectingGraph3 {
	vector<int> edges;
	vector<int> levels;
	int node;
	int find(int x){
		for(int fx=edges[x]; fx; fx=edges[x=fx]);
		return x;
	}
public:
	ConnectingGraph3(int n){
		edges=vector<int>(n+1,0);
		levels=vector<int>(n+1,1);
		node=n;
	}
	/**
	 * @param a: An integer
	 * @param b: An integer
	 * @return: nothing
	 */
	void connect(int a, int b) {
		// write your code here
		a=find(a);
		b=find(b);
		if(a==b) continue;
		if(levels[a]<levels[b]){
			edges[a]=b;
			levels[b]+=levels[a];
		}
		else{
			edges[b]=a;
			levels[a]+=levels[b];
		}
		--node;
	}

	/**
	 * @return: An integer
	 */
	int query() {
		// write your code here
		return node;
	}
};
